高精度计算——算法系列教程(c++版)
梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）
本教程将从高精度计算的核心原理出发，逐步讲解常见高精度运算（加、减、乘、除）的实现逻辑，让大家理解模拟算法的过程，并提供基于C语言的代码示例，帮助读者理解并掌握高精度计算的实现方法。
为什么需要高精度计算？
在常规编程中，我们使用的整数类型（如int、long long）和浮点数类型（如float、double）都有固定的取值范围和精度限制。例如，C语言中的32位int类型取值范围是-2¹⁵到2¹⁵-1（即-32768到32767），64位long long类型的取值范围是-2⁶³到2⁶³-1，约为-9×10¹⁸到9×10¹⁸。而double类型虽然能表示更大范围的数值，但精度仅为15-17位有效数字。
当遇到需要处理超大数值的场景（如大数乘法、阶乘计算、密码学中的大整数运算、科学计算中的高精度需求等）时，常规数据类型会发生溢出或精度丢失，此时就需要通过“高精度计算”技术来模拟人工计算过程，实现对任意长度数值的准确运算。
一、算法原理
1.1 用数组模拟数字存储
高精度计算的核心思路是：将无法用常规数据类型存储的超大数，拆分成单个或多个数字片段，用数组（或字符串）进行存储，然后模拟人类手工计算的步骤(模拟算法)，逐位完成运算，并处理好进位、借位等细节。
模拟算法：不用数学公式推导、不用高级算法，按照问题描述的过程，一步一步用代码原样复刻、模拟执行，让计算机跟着人为的步骤走一遍，就是模拟算法。
关键存储规则：
- 逆序存储：由于运算时需要从低位到高位处理（如加法先算个位，再算十位），而数组的下标从0开始递增，因此通常将数字的低位存储在数组的低下标位置，高位存储在高下标位置。例如，数字123456，逆序存储到数组中为[6,5,4,3,2,1]，其中a[0]=6（个位）、a[1]=5（十位）、a[2]=4（百位），以此类推。
- 长度记录：用一个变量单独记录数字的有效长度（即数组中实际存储的数字位数），避免冗余计算。例如，数组[6,5,4,3,2,1]的有效长度为6。
- 符号处理：对于负数，可单独用一个标志位（如int sign = 1或-1）表示符号，数组中仅存储数字的绝对值。
1.2 数据输入与转换
高精度计算的输入通常是字符串（因为超大数无法直接用数值类型输入），需要将字符串转换为上述的逆序数组存储格式。步骤如下：
- 读取字符串形式的数字（如"123456"）；
- 判断符号（若字符串首字符为'-'，则标记符号位为负，从第二个字符开始处理；否则符号位为正，从第一个字符开始处理）；
- 逆序遍历字符串，将每个字符转换为对应的数字（减去字符'0'），存入数组中；
- 记录数组的有效长度（即数字的位数）。
示例：字符串"123456"转换为数组[6,5,4,3,2,1]，长度为6；字符串"-98765"转换为数组[5,6,7,8,9]，长度为5，符号位为-1。
二、准备阶段
先定义高精度数字的存储结构，再分别实现加、减、乘、除运算。
2.1 定义高精度数字结构
首先定义一个结构体，用于存储高精度数字的符号、有效数字数组和长度：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 定义高精度数字的最大位数（可根据需求调整）
#define MAX_LEN 1000
struct HighPrecision {
int num[MAX_LEN]; // 逆序存储数字的每一位（低位在前，高位在后）
int len; // 有效数字长度
int sign; // 符号位：1为正，-1为负，0为0
};
2.2 初始化高精度数字
实现一个初始化函数，将高精度数字置为0：
// 初始化高精度数字为0
void initHighPrecision(HighPrecision *hp) {
memset(hp->num, 0, sizeof(hp->num)); // 数组清0
hp->len = 0; // 长度为0
hp->sign = 0; // 符号为0（表示数字0）
}
1.3 字符串转高精度数字
实现将字符串转换为高精度数字的函数，这是后续运算的基础：
// 将字符串s转换为高精度数字hp
void strToHighPrecision(const char *s, HighPrecision *hp) {
initHighPrecision(hp); // 先初始化
int len = strlen(s);
int i = 0;
// 判断符号位
if (s[0] == '-') {
hp->sign = -1;
i = 1; // 从第二个字符开始处理数字
} else if (s[0] == '+') {
hp->sign = 1;
i = 1;
} else {
hp->sign = 1; // 默认正数
}
// 逆序存储数字到数组
hp->len = len - i; // 有效数字长度 = 字符串长度 - 符号位长度
len = len - 1;
for (int j = 0; j <= len-i; j++) {
hp->num[j] = s[len-j] - '0'; // 字符转数字
}
// 特殊处理：如果输入是"0"或"-0"，统一置为0
if (hp->len == 1 && hp->num[0] == 0) {
hp->sign = 0;
hp->len = 0;
}
}
1.4 高精度数字转字符串（用于输出）
实现将高精度数字转换为字符串的函数，方便结果输出：
// 将高精度数字hp转换为字符串s（s需要提前分配足够空间）
void highPrecisionToStr(const HighPrecision *hp, char *s) {
if (hp->sign == 0) { // 数字为0
s[0] = '0';
s[1] = '\0';
return;
}
int idx = 0;
// 先写入符号位
if (hp->sign == -1) {
s[idx++] = '-';
}
// 逆序读取数组（从高位到低位）
for (int i = hp->len - 1; i >= 0; i--) {
s[idx++] = hp->num[i] + '0';
}
s[idx] = '\0'; // 字符串结束符
}
三、高精度加法（hp1 + hp2 = res）
3.1 加法原理
高精度加法的核心是模拟人工加法：从低位到高位，逐位相加，同时记录进位（进位值为0或1）。
具体规则：
- sum = hp1.num[i] + hp2.num[i] + 进位;
- res.num[i] = sum % 10; // 当前位结果
- 进位 = sum / 10; // 更新进位
当两个数的所有位都处理完后，若进位不为0，则将进位作为最高位存入结果数组。
注意：加法仅适用于两个正数相加；若有负数，需转换为减法（如a + (-b) = a - b）。
3.2 实现步骤
- 处理符号：若hp1和hp2符号不同，转为减法运算；
- 初始化结果数组、进位为0；
- 遍历两个数的每一位，计算sum = 对应位数字 + 进位；
- 更新结果数组当前位和进位；
- 处理最后剩余的进位；
- 设置结果的符号和长度。
3.3 代码实现
// 高精度加法：hp1 + hp2 = res（需确保hp1和hp2符号相同，不同则调用减法）
void addHighPrecision(const HighPrecision *hp1, const HighPrecision *hp2, HighPrecision *res) {
initHighPrecision(res);
// 若符号不同，转为减法：hp1 + hp2 = hp1 - (-hp2)
if (hp1->sign != hp2->sign) {
HighPrecision temp = *hp2;
temp.sign *= -1;
subHighPrecision(hp1, &temp, res);
return;
}
// 符号相同，执行加法
res->sign = hp1->sign;
int carry = 0; // 进位
int max_len = hp1->len > hp2->len ? hp1->len : hp2->len;
for (int i = 0; i < max_len; i++) {
// 取出当前位数字（若超出长度，补0）
int a = i < hp1->len ? hp1->num[i] : 0;
int b = i < hp2->len ? hp2->num[i] : 0;
int sum = a + b + carry;
res->num[i] = sum % 10;
carry = sum / 10;
res->len++; // 结果长度递增
}
// 处理最后剩余的进位
if (carry != 0) {
res->num[res->len++] = carry;
}
// 特殊处理：结果为0时，符号置为0
if (res->len == 1 && res->num[0] == 0) {
res->sign = 0;
res->len = 0;
}
}
四、高精度减法（hp1 - hp2 = res）
4.1 减法原理
高精度减法的核心是模拟人工减法：从低位到高位，逐位相减，若被减数当前位小于减数当前位，则向高位借位（借位后当前位增加10，高位减少1）。
具体规则：
- 如果需要借位，向高位借1，当前位加10
- res.num[i] = hp1.num[i] - hp2.num[i];
注意：减法需确保被减数大于减数（若不满足，结果取负，转为大数减小数）；若有负数，需转换为加法（如a - (-b) = a + b）。
4.2 实现步骤
- 处理符号：若hp1和hp2符号不同，转为加法运算；
- 比较hp1和hp2的绝对值大小，确定结果符号；
- 用大数减小数（确保被减数绝对值大于减数）；
- 初始化结果数组、借位标记为0；
- 遍历每一位，处理借位并计算差值；
- 去除结果数组的前导零（高位多余的0）；
- 设置结果的符号和长度。
4.3 代码实现
辅助函数：比较两个高精度数字的绝对值大小
// 比较两个高精度数字的绝对值大小：返回1表示hp1绝对值>hp2，-1表示hp1 < hp2，0表示相等
int compareAbs(const HighPrecision *hp1, const HighPrecision *hp2) {
if (hp1->len > hp2->len) {
return 1;
} else if (hp1->len < hp2->len) {
return -1;
} else {
// 长度相等，从高位到低位比较
for (int i = hp1->len - 1; i >= 0; i--) {
if (hp1->num[i] > hp2->num[i]) {
return 1;
} else if (hp1->num[i] < hp2->num[i]) {
return -1;
}
}
return 0; // 所有位都相等
}
}
// 高精度减法：hp1 - hp2 = res
void subHighPrecision(const HighPrecision *hp1, const HighPrecision *hp2, HighPrecision *res) {
initHighPrecision(res);
// 若符号不同，转为加法：hp1 - hp2 = hp1 + (-hp2)
if (hp1->sign != hp2->sign) {
HighPrecision temp = *hp2;
temp.sign *= -1;
addHighPrecision(hp1, &temp, res);
return;
}
// 符号相同，比较绝对值大小
int cmp = compareAbs(hp1, hp2);
if (cmp == 0) { // 两数相等，结果为0
res->sign = 0;
res->len = 0;
return;
}
// 确定结果符号：hp1绝对值大则符号与hp1相同，否则相反
res->sign = cmp == 1 ? hp1->sign : -hp1->sign;
// 用大数减小数（确保被减数绝对值大）
const HighPrecision *big = cmp == 1 ? hp1 : hp2;
const HighPrecision *small = cmp == 1 ? hp2 : hp1;
int borrow = 0; // 借位标记
for (int i = 0; i < big->len; i++) {
int a = big->num[i];
int b = i < small->len ? small->num[i] : 0;
// 处理借位
a = a - borrow;
if (a < b) {
a += 10;
borrow = 1;
} else {
borrow = 0;
}
res->num[i] = a - b;
res->len++;
}
// 去除前导零（高位多余的0）
while (res->len > 0 && res->num[res->len - 1] == 0) {
res->len--;
}
// 特殊处理：结果为0时，符号置为0
if (res->len == 0) {
res->sign = 0;
}
}
五、高精度乘法（hp1 × hp2 = res）
5.1 乘法原理
高精度乘法的核心是模拟人工乘法：用hp1的每一位分别与hp2的每一位相乘，乘积的个位存放在结果数组的i+j位置（i为hp1当前位下标，j为hp2当前位下标），十位作为进位加到i+j+1位置，最后处理所有进位。
具体规则：
- product = a × b;
- res.num[i+j] += product % 10;
- res.num[i+j+1] += product / 10;
所有位相乘完成后，遍历结果数组处理进位（每一位的值加上进位后，取模10作为当前位，除以10作为新的进位）。
注意：乘法结果的符号由两个数的符号决定（同号为正，异号为负）。
5.2 实现步骤
- 处理符号：结果符号 = hp1.sign × hp2.sign；
- 初始化结果数组（长度最大为hp1.len + hp2.len）；
- 双重遍历hp1和hp2的每一位，计算乘积并累加到结果数组对应位置；
- 遍历结果数组，处理进位；
- 去除结果数组的前导零；
- 设置结果的长度和符号。
5.3 代码实现
// 高精度乘法：hp1 × hp2 = res
void mulHighPrecision(const HighPrecision *hp1, const HighPrecision *hp2, HighPrecision *res) {
initHighPrecision(res);
// 特殊情况：有一个数为0，结果为0
if (hp1->sign == 0 || hp2->sign == 0) {
res->sign = 0;
res->len = 0;
return;
}
// 确定结果符号
res->sign = hp1->sign * hp2->sign;
// 初始化结果数组（长度最大为两数长度之和）
res->len = hp1->len + hp2->len;
// 双重遍历，计算每一位的乘积
for (int i = 0; i < hp1->len; i++) {
for (int j = 0; j < hp2->len; j++) {
res->num[i + j] += hp1->num[i] * hp2->num[j];
// 提前处理进位（避免数值过大溢出）
if (res->num[i + j] >= 10) {
res->num[i + j + 1] += res->num[i + j] / 10;
res->num[i + j] %= 10;
}
}
}
// 处理剩余的进位
for (int i = 0; i < res->len; i++) {
if (res->num[i] >= 10) {
res->num[i + 1] += res->num[i] / 10;
res->num[i] %= 10;
}
}
// 去除前导零
while (res->len > 0 && res->num[res->len - 1] == 0) {
res->len--;
}
// 特殊处理：结果为0时，符号置为0
if (res->len == 0) {
res->sign = 0;
}
}
六、高精度除法（hp1 ÷ hp2 = res，求商和余数）
6.1 除法原理
高精度 ÷ 高精度 没有直接的逐位计算方式，唯一实现方法：模拟小学竖式除法的过程(试商法)
从被除数的最高位开始，逐位截取被除数的高位部分，与除数比较：
- 如果截取的部分 < 除数，补下一位继续比较；
- 如果截取的部分 ≥ 除数，做「高精度减法」（被除数截取部分 - 除数），减的次数就是当前位的商；
- 重复上述步骤，直到被除数的所有位处理完毕，最终得到完整的商，减法后剩余的数就是余数。
具体规则：
- 除法要求除数不为0；
- 结果的符号由两个数的符号决定（同号为正，异号为负）；
- 通常需要同时返回商和余数（余数的符号与被除数相同）。
6.2 实现步骤
- 处理特殊情况：除数为0（报错）、被除数为0（商和余数都为0）；
- 处理符号：商的符号 = hp1.sign × hp2.sign；
- 取被除数和除数的绝对值进行运算；
- 初始化商数组；
- 初始化余数数组，从被除数的高至低位截取片断存储到余数(首次截取长度为除数长度)
- 从高位到低位遍历被除数，构建当前被除数片段，试商并更新余数；
- 去除商数组的前导零；
- 设置商和余数的长度和符号。
6.3 代码实现
辅助函数：高精度数字左移一位（相当于乘以10）
// 高精度数字左移一位（乘以10），结果存入res
void leftShiftHighPrecision(const HighPrecision *hp, HighPrecision *res) {
initHighPrecision(res);
if (hp->sign == 0) { // 0左移还是0
res->sign = 0;
return;
}
res->sign = hp->sign;
res->len = hp->len + 1;
// 所有位左移一位，低位补0
for (int i = res->len - 1; i > 0; i--) {
res->num[i] = hp->num[i - 1];
}
res->num[0] = 0;
}
// 高精度除法：hp1 ÷ hp2 = quotient（商） + remainder（余数）
// 要求：hp2不为0；余数的符号与hp1相同，绝对值小于hp2
void divHighPrecision(const HighPrecision *hp1, const HighPrecision *hp2, HighPrecision *quotient, HighPrecision *remainder) {
initHighPrecision(quotient);
initHighPrecision(remainder);
// 特殊情况1：除数为0
if (hp2->sign == 0) {
printf("错误：除数不能为0！\n");
exit(1);
}
// 特殊情况2：被除数为0
if (hp1->sign == 0) {
quotient->sign = 0;
remainder->sign = 0;
return;
}
// 确定商和余数的符号
quotient->sign = hp1->sign * hp2->sign;
remainder->sign = 1;
// 取绝对值进行运算
HighPrecision a, b;
a = *hp1; a.sign = 1;
b = *hp2; b.sign = 1;
// 若被除数绝对值小于除数，商为0，余数为被除数
if (compareAbs(&a, &b) < 0) {
*remainder = *hp1;
quotient->sign = 0;
return;
}
// 初始化商的长度（最大为被除数长度 - 除数长度 + 1）
quotient->len = a.len - b.len + 1;
// 初始化余数，从被除数的高至低位截取片断存储到余数(首次截取长度为除数长度)
int j =0;
remainder->len =0;
for(int i=a.len-b.len;i < a.len;i++)
{
remainder->num[j] = a.num[i];
remainder->len++;
j++;
}
// 从高位到低位遍历被除数，试商
for(int i=a.len-b.len;i>=0;i--)
{
//试商,余数 ≥ 除数，余数 - 除数
while(compareAbs(remainder, &b)>=0) {
HighPrecision temp = *remainder;
sub(&temp, &b, remainder);
quotient->num[i]++; // 记录减的次数
}
// 余数 < 除数，补下一位
if(compareAbs(remainder, &b)==-1)
{
// 余数左移一位，加入被除数的下一位
if(i>0)
{
HighPrecision temp = *remainder;
leftShiftHighPrecision(&temp, remainder);
remainder->num[0] = a.num[i-1];
}
}
}
// 去除商的前导零
while (quotient->len > 0 && quotient->num[quotient->len - 1] == 0) {
quotient->len--;
}
// 去除余数的前导零
while (remainder->len > 0 && remainder->num[remainder->len - 1] == 0) {
remainder->len--;
}
// 特殊处理：商为0时，符号置为0
if (quotient->len == 0) {
quotient->sign = 0;
}
}
七、完整测试示例
以下是一个完整的测试程序，包含上述所有函数，并测试加、减、乘、除运算：
int main() {
HighPrecision hp1, hp2, res, quotient, remainder;
char s1[MAX_LEN * 2], s2[MAX_LEN * 2], s_res[MAX_LEN * 2];
// 测试加法：123456789 + 987654321 = 1111111110
strcpy(s1, "123456789");
strcpy(s2, "987654321");
strToHighPrecision(s1, &hp1);
strToHighPrecision(s2, &hp2);
addHighPrecision(&hp1, &hp2, &res);
highPrecisionToStr(&res, s_res);
printf("加法测试：%s + %s = %s\n", s1, s2, s_res);
// 测试减法：987654321 - 123456789 = 864197532
strcpy(s1, "987654321");
strcpy(s2, "123456789");
strToHighPrecision(s1, &hp1);
strToHighPrecision(s2, &hp2);
subHighPrecision(&hp1, &hp2, &res);
highPrecisionToStr(&res, s_res);
printf("减法测试：%s - %s = %s\n", s1, s2, s_res);
// 测试乘法：123456789 × 987654321 = 121932631112635269
strcpy(s1, "123456789");
strcpy(s2, "987654321");
strToHighPrecision(s1, &hp1);
strToHighPrecision(s2, &hp2);
mulHighPrecision(&hp1, &hp2, &res);
highPrecisionToStr(&res, s_res);
printf("乘法测试：%s × %s = %s\n", s1, s2, s_res);
// 测试除法：121932631112635269 ÷ 123456789 = 987654321
strcpy(s1, "121932631112635269");
strcpy(s2, "123456789");
strToHighPrecision(s1, &hp1);
strToHighPrecision(s2, &hp2);
divHighPrecision(&hp1, &hp2, & quotient, &remainder);
highPrecisionToStr(& quotient, s_res);
char s_remainder[MAX_LEN * 2];
highPrecisionToStr(&remainder, s_remainder);
printf("除法测试：%s ÷ %s = %s，余数 = %s\n", s1, s2, s_res, s_remainder);
return 0;
}
输出结果
加法测试：123456789 + 987654321 = 1111111110
减法测试：987654321 - 123456789 = 864197532
乘法测试：123456789 × 987654321 = 121932631112635269
除法测试：121932631112635269 ÷ 123456789 = 987654321，余数 = 0
八、进阶拓展
8.1 优化方向
- 分段存储>：将多个数字（如4位或8位）合并为一个整数存储在数组中（如用int存储4位数字），减少数组长度，提高运算效率。
- 快速乘法：对于超大数乘法，可使用FFT（快速傅里叶变换）优化，将时间复杂度从O(n²)降低到O(n log n)。
- 内存优化：使用动态数组（如C++的vector）替代固定大小数组，根据实际数字长度分配内存，减少空间浪费。
8.2 常见应用场景
- 密码学：RSA加密算法中的大整数模幂运算；
- 科学计算：需要高精度的物理、化学计算（如分子模拟、天体运行计算）；
- 数学问题：大数阶乘、斐波那契数列的超大项计算、高精度圆周率计算；
- 金融计算：需要精确到分的大额资金计算，避免浮点数精度丢失。
8.3 其他高精度运算
除了上述基本运算，还可基于基础原理实现以下运算：
- 高精度模运算（hp1 % hp2）；
- 高精度幂运算（hp1^hp2，基于快速幂思想）；
- 高精度浮点数运算（需处理小数点位置，模拟小数加法、减法等）。
九、总结
高精度计算的核心是“用数组模拟数字存储，模拟人工运算步骤”，关键在于处理好进位、借位、符号和前导零等细节。本教程从原理出发，实现了高精度加、减、乘、除的基础功能，读者可在此基础上进行优化和拓展。
学习高精度计算的重点在于理解“逐位处理”的思想，通过手动模拟运算过程，再转化为代码实现，就能掌握各类高精度运算的核心逻辑。在实际应用中，可根据需求选择合适的优化方案，平衡运算效率和实现复杂度。
返回顶部